package algorithm.t202112;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/10 16:45
 * @description :1道
 * 今天下午打了新冠第三针，估计是最后一次以学生身份在陕服打疫苗了，下午回来看了看二维前缀和（矩阵和），挺巧妙的，明天去西安看房子，这周也就这样过去了，
 现在这几天都没什么状态，主要是租房这块，等实习了看看能不能换个手机，现在这个手机确实有点不行了，每一天都很快，每一天都是在学习，但是学的多少还是有区别。
 我们在一次次的摸索中调整方向，在一次次的狂风暴雨中坚定自己，在这个残酷的社会，迎接未知的挑战。加油
 persevere to last
 2021.12.10
 李红磊
 2021年12月10日21:20:47
 */
public class t20211210 {
    int[][] dp;

    //求二维数组的矩阵和
    private int tes(int[][] matrix, int x, int y) {
        int rows = matrix.length, columns = matrix[0].length;
        dp = new int[rows][columns];
        //dp[i][j]:表示从(0,0)到(i,j)的矩阵和
        dp[0][0] = matrix[0][0];

        for (int j = 1; j < columns; j++) {
            dp[0][1] = dp[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        return dp[x][y];
    }

    private int getSum(int x1, int y1, int x2, int y2) {
        if (x1 == 0 && y1 == 0) return dp[x2][y2];
        if (x1 == 0) {
            return dp[x2][y2] - dp[x2][y1 - 1];
        }
        if (y1 == 0) {
            return dp[x2][y2] - dp[x1 - 1][y2];
        }

        return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];

    }

    //748.最短补全词
    public String shortestCompletingWord(String licensePlate, String[] words) {
        StringBuffer buffer = new StringBuffer();
        String str = licensePlate.toLowerCase();
        for (int i = 0; i < str.length(); i++) {
            if (Character.isLetter(str.charAt(i))) buffer.append(str.charAt(i));
        }
        char[] ch = buffer.toString().toCharArray();
        Arrays.sort(ch);
        String target = new String(ch);

        String ans = "abcdefghijklmnopqrst";

        for (String element : words) {
            String low = element.toLowerCase();
            char[] c = low.toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if (s.indexOf(target) != -1 && s.length() < ans.length()) ans = element;

        }
        return ans;
    }
    public String shortestCompletingWord2(String licensePlate, String[] words) {

        HashMap<Character, Integer> map = new HashMap<>();
        String s = licensePlate.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetter(s.charAt(i))) map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        String ans = "abcdefghijklmnopqrstuvwxyz";
        HashMap<Character, Integer> w_map = new HashMap<>();

        for (String element : words) {
            boolean flag = true;
            for (int i = 0; i < element.length(); i++)
                w_map.put(element.charAt(i), w_map.getOrDefault(element.charAt(i), 0) + 1);

            for (Character key : map.keySet()) {
                if (map.get(key) > w_map.getOrDefault(key, 0)) {
                    flag = false;
                    break;
                }
            }
            if (flag) if (element.length() < ans.length()) ans = element;
            w_map.clear();
        }


        return ans;
    }

    public static void main(String[] args) {
        t20211210 t20211210 = new t20211210();
        /*int[][] array = new int[][]{
                {1, 5, 6, 8},
                {9, 6, 7, 3},
                {5, 3, 2, 4}
        };
        t20211210.tes(array, 1, 0);
        System.out.println(t20211210.getSum(1, 0, 2, 2));
*/

        System.out.println(t20211210.shortestCompletingWord2("Ah71752"
                , new String[]{"husband", "easy", "education", "drug", "prevent", "writer", "old"}));

        HashMap<Integer, Integer> map = new HashMap<>();

        map.clear();


    }


}
